package DynamicProgramming;//给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
//
// 
//
// 示例 1: 
//
// 输入: [2,3,-2,4]
//输出: 6
//解释: 子数组 [2,3] 有最大乘积 6。
// 
//
// 示例 2: 
//
// 输入: [-2,0,-1]
//输出: 0
//解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 
// Related Topics 数组 动态规划 👍 1320 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class maxProduct {

    public int maxProduct(int[] nums) {

        int len = nums.length;
        if(len==1){
            return nums[0];
        }
        //考虑负数的情况，因此需要最大子数组和最小子数组
        int[] max = new int[len];
        int[] min = new int[len];
        //初始化
        max[0] = nums[0];
        min[0] = nums[0];
        //如果当前是正数，从max中找，负数从min中找
        for(int i=1;i<len;i++){
            if(nums[i] > 0){
                //当前值为正数
                max[i] = Math.max(nums[i], max[i-1] * nums[i]);
                min[i] = Math.min(nums[i], min[i-1] * nums[i]);
            }else{
                //当前值为负数
                max[i] = Math.max(nums[i], min[i-1] * nums[i]);
                min[i] = Math.min(nums[i], max[i-1] * nums[i]);
            }
        }
        return Arrays.stream(max).max().getAsInt();

    }
}
//leetcode submit region end(Prohibit modification and deletion)
